package sword.chapter8Tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 深度优先搜索
 *
 *    1
 *  2   3
 * 4 5 6 7
 *
 * @author K
 * @date 2021/12/6 15:04
 */
public class DFS {
    public static List<Integer> dfs(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        inorderTraversal(root, result);
//        preorderTraversal(root, result);
//        postorderTraversal(root, result);
        return result;
    }

    /**
     * 中序遍历
     * 左树 -> 根节点 -> 右树（中间位置存值）
     * 4 2 5 1 6 3 7
     */
    private static void inorderTraversal(TreeNode root, LinkedList<Integer> result) {
        if (root != null) {
            inorderTraversal(root.left, result);
            result.add(root.val);
            inorderTraversal(root.right, result);
        }
    }

    /**
     * 栈-中序遍历 后入先出
     */
    private static List<Integer> stackInorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 一直遍历左树节点，并放入栈中
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            result.add(cur.val);
            // 遍历右树节点
            cur = cur.right;
        }

        return result;
    }

    /**
     * 前序遍历
     * 根节点 -> 左树 -> 右树（一开始就存值）
     * 1 2 4 5 3 6 7
     */
    private static void preorderTraversal(TreeNode root, LinkedList<Integer> result) {
        if (root != null) {
            result.add(root.val);
            preorderTraversal(root.left, result);
            preorderTraversal(root.right, result);
        }
    }

    /**
     * 栈-前序遍历 后入先出
     */
    private static List<Integer> stackPreorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 一直遍历左树节点，并放入栈中
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                result.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            // 遍历右树节点
            cur = cur.right;
        }

        return result;
    }

    /**
     * 后序遍历
     * 左树 -> 右树 -> 根节点（最后存值）
     * 4 5 2 6 7 3 1
     */
    private static void postorderTraversal(TreeNode root, LinkedList<Integer> result) {
        if (root != null) {
            postorderTraversal(root.left, result);
            postorderTraversal(root.right, result);
            result.add(root.val);
        }
    }

    /**
     * 栈-后序遍历 后入先出
     */
    private static List<Integer> stackPostorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        // 一直遍历左树节点，并放入栈中
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.peek();
            if (cur.right != null && cur.right != prev) {
                cur = cur.right;
            } else {
                stack.pop();
                result.add(cur.val);
                prev = cur;
                cur = null;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        List<Integer> result = dfs(root);
        List<Integer> result1 = stackInorderTraversal(root);
        List<Integer> result2 = stackPreorderTraversal(root);
        List<Integer> result3 = stackPostorderTraversal(root);
        System.out.println();
    }
}

/**
 * 二叉树
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
